<!DOCTYPE html>
<html lang="zh-cn">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
  <link rel="icon" type="image/png" sizes="16x16" href="https://gitee.com/reku1997/reku1997/raw/master/reku.ico">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"reku1997.gitee.io","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":"flat"},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"appID":"AW5K8S9IEE","apiKey":"d7e666d597854738d2fb31ecaa989aa5","indexName":"dev_reku1997","hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}}};
  </script>

  <meta name="description" content="There are n boys. All of them are friends. They live in all over the world. One day, one of them wants to know the farthest distance between two boys. Now, you are given the positions of boys. Two bo">
<meta property="og:type" content="article">
<meta property="og:title" content="计算几何模板题">
<meta property="og:url" content="https://reku1997.gitee.io/2016/07/10/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95%E6%A8%A1%E6%9D%BF/index.html">
<meta property="og:site_name" content="Reku">
<meta property="og:description" content="There are n boys. All of them are friends. They live in all over the world. One day, one of them wants to know the farthest distance between two boys. Now, you are given the positions of boys. Two bo">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2016-07-10T07:04:55.000Z">
<meta property="article:modified_time" content="2020-06-09T12:01:18.000Z">
<meta property="article:author" content="Reku">
<meta property="article:tag" content="计算几何">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="https://reku1997.gitee.io/2016/07/10/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95%E6%A8%A1%E6%9D%BF/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-cn'
  };
</script>

  <title>计算几何模板题 | Reku</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/atom.xml" title="Reku" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="Toggle navigation bar">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">Reku</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>Home</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-fw fa-user"></i>About</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>Tags</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>Archives</a>

  </li>
        <li class="menu-item menu-item-sitemap">

    <a href="/sitemap.xml" rel="section"><i class="fa fa-fw fa-sitemap"></i>Sitemap</a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>Search
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container"></div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div class="algolia-results">
  <div id="algolia-stats"></div>
  <div id="algolia-hits"></div>
  <div id="algolia-pagination" class="algolia-pagination"></div>
</div>

      
    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-cn">
    <link itemprop="mainEntityOfPage" href="https://reku1997.gitee.io/2016/07/10/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95%E6%A8%A1%E6%9D%BF/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="Reku">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Reku">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          计算几何模板题
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">Posted on</span>

              <time title="Created: 2016-07-10 15:04:55" itemprop="dateCreated datePublished" datetime="2016-07-10T15:04:55+08:00">2016-07-10</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">Edited on</span>
                <time title="Modified: 2020-06-09 20:01:18" itemprop="dateModified" datetime="2020-06-09T20:01:18+08:00">2020-06-09</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">In</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/acm/" itemprop="url" rel="index"><span itemprop="name">acm</span></a>
                </span>
            </span>

          
            <span id="/2016/07/10/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95%E6%A8%A1%E6%9D%BF/" class="post-meta-item leancloud_visitors" data-flag-title="计算几何模板题" title="Views">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">Views: </span>
              <span class="leancloud-visitors-count"></span>
            </span>
  
  <span class="post-meta-item">
    
      <span class="post-meta-item-icon">
        <i class="fa fa-comment-o"></i>
      </span>
      <span class="post-meta-item-text">Valine: </span>
    
    <a title="valine" href="/2016/07/10/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95%E6%A8%A1%E6%9D%BF/#valine-comments" itemprop="discussionUrl">
      <span class="post-comments-count valine-comment-count" data-xid="/2016/07/10/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95%E6%A8%A1%E6%9D%BF/" itemprop="commentCount"></span>
    </a>
  </span>
  
  

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <blockquote>
<p>There are n boys. All of them are friends. They live in all over the world. One day, one of them wants to know the farthest distance between two boys. Now, you are given the positions of boys. Two boys may in the same position. Your are required to tell boys the farthest distance. Input The first line is one integer n.(1 ≤ n ≤ 105) Each of next n lines has two integers xi and yi, which means the i-th boy's position. (0 ≤ xi, yi ≤ 1010) There are multiple test cases, please stop when n = 0. Output One line for each test case containing a real number in three decimal places.</p>
</blockquote>
<span id="more"></span>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> using namespace std;</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> rel_ops;</span><br><span class="line"></span><br><span class="line"><span class="comment">// typedef long long NUM;</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">double</span> NUM;</span><br><span class="line"><span class="keyword">const</span> NUM EPS = <span class="number">1e-12</span>, MAGIC = <span class="number">2.71828e18</span>;</span><br><span class="line"><span class="comment">// 因为有相对误差判断，所以EPS不要设得太宽</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> NUM <span class="title">sqr</span><span class="params">(NUM a)</span></span>&#123;<span class="keyword">return</span> a*a;&#125;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> NUM <span class="title">cmp</span><span class="params">(NUM a, NUM b)</span></span>&#123;</span><br><span class="line">    <span class="comment">// return a-b; // 坐标为浮点数时，使用下面这行</span></span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">fabs</span>(a-b)&gt;=EPS+<span class="built_in">fabs</span>(a)*EPS?a-b:<span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//--------------------------------------------------------------------//</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">VEC</span> &#123;</span>NUM x,y;&#125; NOVEC = &#123;MAGIC,MAGIC&#125;;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">RAY</span> &#123;</span>VEC u,v;&#125; NORAY = &#123;NOVEC,NOVEC&#125;;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">CIR</span> &#123;</span>VEC u; NUM r;&#125; NOCIR = &#123;NOVEC,MAGIC&#125;;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> NUM <span class="title">sqr</span><span class="params">(<span class="keyword">const</span> VEC&amp; a)</span></span>&#123;<span class="keyword">return</span> <span class="built_in">sqr</span>(a.x)+<span class="built_in">sqr</span>(a.y);&#125;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">double</span> <span class="title">abs</span><span class="params">(<span class="keyword">const</span> VEC&amp; a)</span></span>&#123;<span class="keyword">return</span> <span class="built_in">sqrt</span>(<span class="built_in">sqr</span>(a));&#125;</span><br><span class="line"><span class="function"><span class="keyword">inline</span> NUM <span class="title">cmp</span><span class="params">(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b)</span></span>&#123;</span><br><span class="line">    NUM at=<span class="built_in">cmp</span>(a.x,b.x);</span><br><span class="line">    <span class="keyword">return</span> !at?<span class="built_in">cmp</span>(a.y,b.y):at;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">inline</span> VEC <span class="keyword">operator</span> +(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b)</span><br><span class="line">    &#123;<span class="keyword">return</span> (VEC)&#123;a.x+b.x,a.y+b.y&#125;;&#125;</span><br><span class="line"><span class="keyword">inline</span> VEC <span class="keyword">operator</span> -(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b)</span><br><span class="line">    &#123;<span class="keyword">return</span> (VEC)&#123;a.x-b.x,a.y-b.y&#125;;&#125;</span><br><span class="line"><span class="keyword">inline</span> NUM <span class="keyword">operator</span> *(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b)</span><br><span class="line">    &#123;<span class="keyword">return</span> a.x*b.y-a.y*b.x;&#125;</span><br><span class="line"><span class="keyword">inline</span> NUM <span class="keyword">operator</span> %(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b)</span><br><span class="line">    &#123;<span class="keyword">return</span> a.x*b.x+a.y*b.y;&#125;</span><br><span class="line"><span class="keyword">inline</span> VEC <span class="keyword">operator</span> -(<span class="keyword">const</span> VEC&amp; a)&#123;<span class="keyword">return</span> (VEC)&#123;-a.x,-a.y&#125;;&#125;</span><br><span class="line"><span class="keyword">inline</span> VEC <span class="keyword">operator</span> ~(<span class="keyword">const</span> VEC&amp; a)&#123;<span class="keyword">return</span> (VEC)&#123;-a.y,+a.x&#125;;&#125;</span><br><span class="line"><span class="keyword">inline</span> VEC <span class="keyword">operator</span> *(NUM u, <span class="keyword">const</span> VEC&amp; a)&#123;<span class="keyword">return</span> (VEC)&#123;u*a.x,u*a.y&#125;;&#125;</span><br><span class="line"><span class="keyword">inline</span> VEC <span class="keyword">operator</span> *(<span class="keyword">const</span> VEC&amp; a, NUM u)&#123;<span class="keyword">return</span> (VEC)&#123;a.x*u,a.y*u&#125;;&#125;</span><br><span class="line"><span class="keyword">inline</span> VEC <span class="keyword">operator</span> /(<span class="keyword">const</span> VEC&amp; a, NUM u)&#123;<span class="keyword">return</span> (VEC)&#123;a.x/u,a.y/u&#125;;&#125;</span><br><span class="line"><span class="keyword">inline</span> VEC <span class="keyword">operator</span> /(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b)&#123;<span class="keyword">return</span> a%b/<span class="built_in">sqr</span>(b)*b;&#125;</span><br><span class="line"><span class="keyword">inline</span> <span class="keyword">bool</span> <span class="keyword">operator</span> ==(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b)&#123;<span class="keyword">return</span> !<span class="built_in">cmp</span>(a,b);&#125;</span><br><span class="line"><span class="keyword">inline</span> <span class="keyword">bool</span> <span class="keyword">operator</span> &lt;(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b)&#123;<span class="keyword">return</span> <span class="built_in">cmp</span>(a,b)&lt;<span class="number">0</span>;&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//  返回值        cmp_side             cmp_axis</span></span><br><span class="line"><span class="comment">//  ==  0       a和b相互平行    /    a和b相互垂直</span></span><br><span class="line"><span class="comment">//  &lt;= -EPS     a在b的左手侧    /    a和b朝向相反（内角大于90度）</span></span><br><span class="line"><span class="comment">//  &gt;= +EPS     a在b的右手侧    /    a和b朝向相同（内角小于90度）</span></span><br><span class="line"><span class="function">NUM <span class="title">cmp_side</span><span class="params">(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b)</span></span>&#123;<span class="keyword">return</span> <span class="built_in">cmp</span>(a.x*b.y,+a.y*b.x);&#125;</span><br><span class="line"><span class="function">NUM <span class="title">cmp_axis</span><span class="params">(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b)</span></span>&#123;<span class="keyword">return</span> <span class="built_in">cmp</span>(a.x*b.x,-a.y*b.y);&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//--------------------------------------------------------------------//</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 求向量a长度缩放至u单位后的新向量，a不能是零向量</span></span><br><span class="line"><span class="comment">// 求向量a绕坐标原点o，逆时针转u度后的新向量</span></span><br><span class="line"><span class="function">VEC <span class="title">resize</span><span class="params">(<span class="keyword">const</span> VEC&amp; a, NUM u)</span></span>&#123;<span class="keyword">return</span> u/<span class="built_in">abs</span>(a)*a;&#125;</span><br><span class="line"><span class="function">VEC <span class="title">rotate</span><span class="params">(<span class="keyword">const</span> VEC&amp; a, NUM u)</span></span></span><br><span class="line"><span class="function">    </span>&#123;<span class="keyword">return</span> (VEC)&#123;<span class="built_in">cos</span>(u)*a.x-<span class="built_in">sin</span>(u)*a.y,<span class="built_in">sin</span>(u)*a.x+<span class="built_in">cos</span>(u)*a.y&#125;;&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 点在直线上的投影(到直线的最近点)</span></span><br><span class="line"><span class="comment">// 点在圆周上的投影(到圆周的最近点)</span></span><br><span class="line"><span class="function">VEC <span class="title">project</span><span class="params">(<span class="keyword">const</span> VEC&amp; p, <span class="keyword">const</span> RAY&amp; l)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (p-l.u)/(l.v-l.u)+l.u;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function">VEC <span class="title">project</span><span class="params">(<span class="keyword">const</span> VEC&amp; p, <span class="keyword">const</span> CIR&amp; c)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(!<span class="built_in">cmp</span>(p,c.u)) <span class="keyword">return</span> NOVEC;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">resize</span>(p-c.u,c.r)+c.u;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 求两直线的交点</span></span><br><span class="line"><span class="comment">// 求直线与圆的交点，交线段的方向与原先直线相同</span></span><br><span class="line"><span class="comment">// 求两圆相交的交点，交线段的方向为圆心a到b连线方向逆指针转90度</span></span><br><span class="line"><span class="comment">// 求直线与凸多边形的交点，交线段的方向与原先直线相同，复杂度O(logn)</span></span><br><span class="line"><span class="function">VEC <span class="title">intersect</span><span class="params">(<span class="keyword">const</span> RAY&amp; a, <span class="keyword">const</span> RAY&amp; b)</span></span>&#123;</span><br><span class="line">    VEC s=a.u-a.v,t=b.u-b.v;</span><br><span class="line">    NUM at=<span class="built_in">cmp_side</span>(s,t);</span><br><span class="line">    <span class="keyword">if</span>(!at) <span class="keyword">return</span> NOVEC;</span><br><span class="line">    <span class="keyword">return</span> a.u+(b.u-a.u)*t/at*s;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function">RAY <span class="title">intersect</span><span class="params">(<span class="keyword">const</span> RAY&amp; l, <span class="keyword">const</span> CIR&amp; c)</span></span>&#123;</span><br><span class="line">    VEC s=l.u+(c.u-l.u)/(l.v-l.u);</span><br><span class="line">    NUM at=<span class="built_in">cmp</span>(c.r*c.r,<span class="built_in">sqr</span>(s-c.u));</span><br><span class="line">    <span class="keyword">if</span>(at&lt;<span class="number">0</span>) <span class="keyword">return</span> NORAY;</span><br><span class="line">    VEC t=<span class="built_in">resize</span>(l.v-l.u,<span class="built_in">sqrt</span>(at));</span><br><span class="line">    <span class="keyword">return</span> (RAY)&#123;s-t,s+t&#125;;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function">RAY <span class="title">intersect</span><span class="params">(<span class="keyword">const</span> CIR&amp; a, <span class="keyword">const</span> CIR&amp; b)</span></span>&#123;</span><br><span class="line">    NUM l=<span class="built_in">sqr</span>(b.u-a.u);</span><br><span class="line">    NUM w=(<span class="number">1</span>+(a.r*a.r-b.r*b.r)/l)*<span class="number">0.5</span>;</span><br><span class="line">    NUM e=<span class="built_in">cmp</span>(a.r*a.r/l,w*w);</span><br><span class="line">    <span class="keyword">if</span>(e&lt;<span class="number">0</span>) <span class="keyword">return</span> NORAY;</span><br><span class="line">    VEC t=<span class="built_in">sqrt</span>(e)*~(b.u-a.u);</span><br><span class="line">    VEC s=a.u+w*(b.u-a.u);</span><br><span class="line">    <span class="keyword">return</span> (RAY)&#123;s-t,s+t&#125;;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 判断三点是否共线</span></span><br><span class="line"><span class="comment">// 判断点在直线上的投影点，是否在线段上</span></span><br><span class="line"><span class="comment">// 判断点和线的位置关系，在外侧为0，在直线上为1或2(在线段上时为2)</span></span><br><span class="line"><span class="comment">// 判断点和圆的位置关系，在外侧为0，内部为1，边上为2</span></span><br><span class="line"><span class="comment">// 判断点和任意简单多边形的位置关系，在外侧为0，内部为1，边上为2</span></span><br><span class="line"><span class="comment">// 快速地判断点和凸多边形的位置关系，在外侧为0，内部为1，边上为2</span></span><br><span class="line"><span class="comment">// 判断两条线的位置关系，斜相交为0，垂直为1，平行为2，重合为3</span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">collinear</span><span class="params">(<span class="keyword">const</span> VEC&amp; a, <span class="keyword">const</span> VEC&amp; b, <span class="keyword">const</span> VEC&amp; c)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> !<span class="built_in">cmp_side</span>(a-b,b-c);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">seg_range</span><span class="params">(<span class="keyword">const</span> VEC&amp; p, <span class="keyword">const</span> RAY&amp; l)</span></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">cmp_axis</span>(p-l.u,p-l.v)&lt;=<span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">relation</span><span class="params">(<span class="keyword">const</span> VEC&amp; p, <span class="keyword">const</span> RAY&amp; l)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">cmp_side</span>(p-l.u,p-l.v)) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">cmp_axis</span>(p-l.u,p-l.v)&gt;<span class="number">0</span>?<span class="number">1</span>:<span class="number">2</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">relation</span><span class="params">(<span class="keyword">const</span> VEC&amp; p, <span class="keyword">const</span> CIR&amp; c)</span></span>&#123;</span><br><span class="line">    NUM at=<span class="built_in">cmp</span>(<span class="built_in">sqr</span>(c.r),<span class="built_in">sqr</span>(c.u-p));</span><br><span class="line">    <span class="keyword">return</span> at?at&lt;<span class="number">0</span>?<span class="number">0</span>:<span class="number">1</span>:<span class="number">2</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">relation</span><span class="params">(<span class="keyword">const</span> VEC&amp; p, <span class="keyword">const</span> vector&amp; u)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n=u.<span class="built_in">size</span>(),ret=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i0</span><br><span class="line">        &amp;&amp; <span class="built_in">cmp_side</span>(s,t)&gt;<span class="number">0</span>) ret^=<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ret;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">relation_convex</span><span class="params">(<span class="keyword">const</span> VEC&amp; p, <span class="keyword">const</span> vector&amp; u)</span></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n=u.<span class="built_in">size</span>(),l=<span class="number">0</span>,r=n<span class="number">-1</span>,o=<span class="built_in">cmp_side</span>(u[<span class="number">1</span>]-u[<span class="number">0</span>],u[r]-u[<span class="number">0</span>])&lt;<span class="number">0</span>?<span class="number">-1</span>:<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">relation</span>(p,(RAY)&#123;u[<span class="number">0</span>],u[<span class="number">1</span>]&#125;)==<span class="number">2</span></span><br><span class="line">    || <span class="built_in">relation</span>(p,(RAY)&#123;u[<span class="number">0</span>],u[r]&#125;)==<span class="number">2</span>) <span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">while</span>(l <span class="built_in">tangent</span>(<span class="keyword">const</span> CIR&amp; a, <span class="keyword">const</span> CIR&amp; b)&#123;</span><br><span class="line">    NUM o=a.r-b.r,l=<span class="built_in">sqr</span>(b.u-a.u),e=<span class="built_in">cmp</span>(l,o*o);</span><br><span class="line">    <span class="keyword">if</span>(e&lt;<span class="number">0</span>) <span class="keyword">return</span> <span class="built_in">make_pair</span>(NORAY,NORAY);</span><br><span class="line">    NUM x=o/<span class="built_in">sqrt</span>(l),y=<span class="built_in">sqrt</span>(e/l);</span><br><span class="line">    VEC s=<span class="built_in">resize</span>(b.u-a.u,<span class="number">1</span>),t=~s;</span><br><span class="line">    RAY ll=&#123;a.u+a.r*x*s+a.r*y*t,</span><br><span class="line">            b.u+b.r*x*s+b.r*y*t&#125;;</span><br><span class="line">    RAY rr=&#123;a.u+a.r*x*s-a.r*y*t,</span><br><span class="line">            b.u+b.r*x*s-b.r*y*t&#125;;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">make_pair</span>(ll,rr);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 由散点集构造一个最小覆盖圆，期望复杂度O(n)</span></span><br><span class="line">CIR <span class="built_in">min_covering_circle</span>(vector u)&#123;</span><br><span class="line">    <span class="built_in">random_shuffle</span>(u.<span class="built_in">begin</span>(),u.<span class="built_in">end</span>());</span><br><span class="line">    <span class="keyword">int</span> n=u.<span class="built_in">size</span>(),i,j,k,z=<span class="number">1</span>%n;</span><br><span class="line">    CIR ret;</span><br><span class="line">    <span class="keyword">for</span>(ret=<span class="built_in">make_circle</span>(u[<span class="number">0</span>],u[z]),i=<span class="number">2</span>;i <span class="built_in">convex_hull</span>(vector u)&#123;</span><br><span class="line">    <span class="built_in">sort</span>(u.<span class="built_in">begin</span>(),u.<span class="built_in">end</span>()); <span class="comment">// 这两行是排序+去重，如果数据已经有保证</span></span><br><span class="line">    u.<span class="built_in">erase</span>(<span class="built_in">unique</span>(u.<span class="built_in">begin</span>(),u.<span class="built_in">end</span>()),u.<span class="built_in">end</span>()); <span class="comment">// 则可省略相应的操作</span></span><br><span class="line">    <span class="keyword">if</span>(u.<span class="built_in">size</span>()&lt;<span class="number">3</span>) <span class="keyword">return</span> u;</span><br><span class="line">    vector c;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">size_t</span> i=<span class="number">0</span>,o=<span class="number">1</span>,m=<span class="number">1</span>;~i;i+=o)&#123;</span><br><span class="line">        <span class="keyword">while</span>(c.<span class="built_in">size</span>()&gt;m)&#123;</span><br><span class="line">            VEC a=c.<span class="built_in">back</span>()-c[c.<span class="built_in">size</span>()<span class="number">-2</span>];</span><br><span class="line">            VEC b=c.<span class="built_in">back</span>()-u[i];</span><br><span class="line">            <span class="keyword">if</span>(<span class="built_in">cmp_side</span>(a,b)&lt;<span class="number">0</span>) <span class="keyword">break</span>; <span class="comment">// 改成&lt;=0则保留共线点</span></span><br><span class="line">            c.<span class="built_in">pop_back</span>();</span><br><span class="line">        &#125;</span><br><span class="line">        c.<span class="built_in">push_back</span>(u[i]);</span><br><span class="line">        <span class="keyword">if</span>(i+<span class="number">1</span>==u.<span class="built_in">size</span>()) m=c.<span class="built_in">size</span>(),o=<span class="number">-1</span>; <span class="comment">// 条件成立时切换至上凸壳</span></span><br><span class="line">    &#125;</span><br><span class="line">    c.<span class="built_in">pop_back</span>();</span><br><span class="line">    <span class="keyword">return</span> c;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//两个点的距离</span></span><br><span class="line"><span class="keyword">double</span> <span class="built_in">ff</span>(VEC a,VEC b)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">double</span> l=<span class="built_in">fabs</span>(a.x-b.x);</span><br><span class="line">    <span class="keyword">double</span> r=<span class="built_in">fabs</span>(a.y-b.y);</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">sqrt</span>(l*l+r*r);</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//叉积</span></span><br><span class="line"><span class="keyword">double</span> <span class="built_in">Cross</span>(VEC A,VEC B,VEC C)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="built_in"><span class="keyword">return</span></span> (B-A)*(C-B);</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//旋转卡壳</span></span><br><span class="line"><span class="keyword">double</span> <span class="built_in">rr</span>(vector u)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">int</span> q=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">double</span> ans=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> n=u.<span class="built_in">size</span>();</span><br><span class="line">    u.<span class="built_in">push_back</span>(u[<span class="number">0</span>]);</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> p=<span class="number">0</span>;<span class="built_in">pCross</span>(u[p],u[q+<span class="number">1</span>],u[p+<span class="number">1</span>])) q=(q+<span class="number">1</span>)%n;</span><br><span class="line">        ans=<span class="built_in">max</span>(ans,<span class="built_in">max</span>(<span class="built_in">ff</span>(u[p],u[q]),<span class="built_in">ff</span>(u[p+<span class="number">1</span>],u[q])));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">int</span> n;</span><br><span class="line"><span class="keyword">void</span> <span class="built_in">work</span>()</span><br><span class="line">&#123;</span><br><span class="line">    vector u;</span><br><span class="line">    VEC p;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=n;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%lf%lf&quot;</span>,&amp;p.x,&amp;p.y);</span><br><span class="line">        u.<span class="built_in">push_back</span>(p);</span><br><span class="line">    &#125;</span><br><span class="line">    vector ans;</span><br><span class="line">    ans=<span class="built_in">convex_hull</span>(u);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%.3lf\n&quot;</span>,<span class="built_in">rr</span>(ans));</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">int</span> <span class="built_in">main</span>()</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">while</span>(<span class="number">1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">        <span class="keyword">if</span>(n==<span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="built_in">work</span>();</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95/" rel="tag"># 计算几何</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2016/07/09/%E7%BB%84%E5%90%88%E6%95%B0%E5%8F%96%E6%A8%A1/" rel="prev" title="组合数取模">
      <i class="fa fa-chevron-left"></i> 组合数取模
    </a></div>
      <div class="post-nav-item">
    <a href="/2016/07/15/%E5%BF%AB%E9%80%9F%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2/" rel="next" title="快速傅里叶变换">
      快速傅里叶变换 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          
    <div class="comments" id="valine-comments"></div>

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          Table of Contents
        </li>
        <li class="sidebar-nav-overview">
          Overview
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">Reku</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">78</span>
          <span class="site-state-item-name">posts</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
        <span class="site-state-item-count">8</span>
        <span class="site-state-item-name">categories</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">96</span>
        <span class="site-state-item-name">tags</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/wyc-ruiker" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;wyc-ruiker" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.zhihu.com/people/reku1997" title="ZhiHu → https:&#x2F;&#x2F;www.zhihu.com&#x2F;people&#x2F;reku1997" rel="noopener" target="_blank"><i class="fa fa-fw fa-quora"></i>ZhiHu</a>
      </span>
      <span class="links-of-author-item">
        <a href="http://codeforces.com/profile/reku" title="CodeForces → http:&#x2F;&#x2F;codeforces.com&#x2F;profile&#x2F;reku" rel="noopener" target="_blank"><i class="fa fa-fw fa-code"></i>CodeForces</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://www.linkedin.cn/injobs/in/reku" title="Linkedin → https:&#x2F;&#x2F;www.linkedin.cn&#x2F;injobs&#x2F;in&#x2F;reku" rel="noopener" target="_blank"><i class="fa fa-fw fa-linkedin"></i>Linkedin</a>
      </span>
      <span class="links-of-author-item">
        <a href="https://gitee.com/reku1997" title="Gitee → https:&#x2F;&#x2F;gitee.com&#x2F;reku1997" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>Gitee</a>
      </span>
      <span class="links-of-author-item">
        <a href="/./atom.xml" title="RSS → .&#x2F;atom.xml"><i class="fa fa-fw fa-rss"></i>RSS</a>
      </span>
  </div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 2016 – 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Reku</span>
</div>
  <div class="powered-by">Powered by <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a>
  </div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="Total Visitors">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="Total Views">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="//cdn.jsdelivr.net/npm/algoliasearch@4/dist/algoliasearch-lite.umd.js"></script>
<script src="//cdn.jsdelivr.net/npm/instantsearch.js@4/dist/instantsearch.production.min.js"></script>
<script src="/js/algolia-search.js"></script>














  

  

  


<script>
NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
  NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
    var GUEST = ['nick', 'mail', 'link'];
    var guest = 'nick,mail,link';
    guest = guest.split(',').filter(item => {
      return GUEST.includes(item);
    });
    new Valine({
      el         : '#valine-comments',
      verify     : false,
      notify     : false,
      appId      : 'MWLzM550UOu69h3dgvbbLSsF-gzGzoHsz',
      appKey     : 'gkKnwm9FK0cu3ysJbcggsCDz',
      placeholder: "Just go go",
      avatar     : 'mm',
      meta       : guest,
      pageSize   : '10' || 10,
      visitor    : true,
      lang       : '' || 'zh-cn',
      path       : location.pathname,
      recordIP   : false,
      serverURLs : ''
    });
  }, window.Valine);
});
</script>

</body>
</html>
